BZOJ1015【JSOI2008】星球大战 <离线并查集>

Problem

【JSOI2008】星球大战

题目描述

很久以前，在一个遥远的星系，一个黑暗的帝国靠着它的超级武器统治者整个星系。某一天，凭着一个偶然的机遇，一支反抗军摧毁了帝国的超级武器，并攻下了星系中
几乎所有的星球。这些星球通过特殊的以太隧道互相直接或间接地连接。但好景不长，很快帝国又重新造出了他的超级武器。凭借这超级武器的力量，帝国开始有计划地
摧毁反抗军占领的星球。由于星球的不断被摧毁，两个星球之间的通讯通道也开始不可靠起来。现在，反抗军首领交给你一个任务：给出原来两个星球之间的以太隧道连
通情况以及帝国打击的星球顺序，以尽量快的速度求出每一次打击之后反抗军占据的星球的连通快的个数。（如果两个星球可以通过现存的以太通道直接或间接地连通，
则这两个星球在同一个连通块中）。

输入输出格式

输入格式
输入文件第一行包含两个整数，和，分别表示星球的数目和以太隧道的数目。星球用的整数编号。
接下来的行，每行包括两个整数，其中（且），表示星球和星球之间有以太隧道。注意所有的以太隧道都是双向的。
接下来一行是一个整数，表示帝国计划打击的星球个数。
接下来的行每行一个整数，满足，表示帝国计划打击的星球编号。帝国总是按输入的顺序依次摧毁星球的。
输出格式
输出文件的第一行是开始时星球的连通块个数。
接下来的行，每行一个整数，表示经过该次打击后现存星球的连通块个数。

输入输出样例

输入样例

输出样例

标签：离线并查集

Solution

并查集水题。因为只会删边，不会增边，因此我们从最后时刻往前面模拟，每次加边（从最后一条边往前加），加边后输出联通块个数即可。

Code

#include <iostream>
#include <cstdio>
#include <vector>
#include <stack>
#define MAX_N 400000
#define MAX_M 200000
using namespace std;
int n, m, k, cnt;
int f[MAX_N+5], mark[MAX_N+5], opt[MAX_N+5];
vector <int> edge[MAX_N+5];
stack <int> ans;
int find(int v) {
    if (f[v] == v)
        return v;
    return f[v] = find(f[v]);
}
void merge(int v) {
    if (mark[v])    cnt++;
    for (int i = 0; i < edge[v].size(); i++) {
        int u = edge[v][i];
        if (mark[u])    continue;
        int anc1 = find(v);
        int anc2 = find(u);
        if (anc1 != anc2)
            cnt--, f[anc1] = anc2;
    }
    mark[v] = 0;
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < m; i++) {
        int x, y;	scanf("%d%d", &x, &y);
        edge[x].push_back(y);
        edge[y].push_back(x);
    }
    for (int i = 0; i < n; i++)    f[i] = i;
    scanf("%d", &k);
    for (int i = 1; i <= k; i++) {
        scanf("%d", &opt[i]);
        mark[opt[i]] = 1;
    }
    cnt = n-k;
    for (int i = 0; i < n; i++)
        if (!mark[i])
            merge(i);
    ans.push(cnt);
    for (int i = k; i >= 1; i--) {
        merge(opt[i]);
        ans.push(cnt);
    }
    while (!ans.empty()) {
        printf("%d\n", ans.top());
        ans.pop();
    }
    return 0;
}